1. Field of the Invention
The present invention relates to a local area network (LAN) employing the Ethernet and more particularly to a method for improving scheduling fairness of signal transmission/reception in a network when collisions occur in an Ethernet based LAN.
2. Background of the Related Art
Generally, all nodes can access a network with fair scheduling priority in a CSMA/CD (Carrier Sense Multiple Access with Collision Detection) system. All the nodes must confirm that the network is not used for a time interval of an inter packet gap (IPG) before transmitting a packet. The IPG is typically about 9.6 xcexcs for a 10M network and 0.96 xcexcs at a 100M network. However, a collision occurs when two nodes transmit a packet simultaneously.
FIG. 1 illustrates channel access processing in a conventional Ethernet based LAN. As shown in FIG. 1, all m nodes, from the first node S1, to the mth node Sm, transmit a first packet. After the transmission is completed, the nodes S1 to Sm wait for up to the IPG duration before transmitting a second packet. After the transmission of the second packet is completed, the first node S1 to the next to last node Sm wait for the IPG and then transmit a third packet. However, the mth node Sm delays for the IPG after finishing the transmission of the second packet and then transmits a fourth packet. If the first node S1 and the mth node Sm simultaneously transmit their packets, then a conflict or collision occurs after xc2xd slot time. In FIG. 1, a collision occurs between the fourth packets transmitted from nodes S1 and Sm.
If the collision occurs, each node that transmitted the colliding packets waits as long as the IPG plus a backoff time before retransmitting the same packet. The backoff time is set differently for each node to prevent another collision. Each node that transmits a colliding packet repeats the transmission immediately after a lapse of the predetermined backoff time until the packet is successfully transmitted or until the number of retransmission trials or attempts due to collisions exceeds a predetermined maximum number and the trial terminates.
One related process for setting the backoff time is called a truncated binary exponential backoff algorithm. FIG. 2 illustrates a channel capture effect occurring when using such a related backoff algorithm. The backoff time is set to an integral multiple number r of a slot time. The slot time is a maximum turnaround time delay in the network. In other words, the time slot is a maximum time necessary for a certain node to transmit a packet and receive an answer. For example, the slot time in a 10M network is 51.2 xcexcs.
The integral multiple number r that will be multiplied by the slot time is determined based on the number of times the packet is retransmitted by the node in accordance with the following formula:
0xe2x89xa6r less than 2k, where variable k=min (n, 10), n is the number of times of signal retransmission and 10 is the predetermined maximum number of retransmission attempts before the trial terminates.
Table 1 illustrates the values of the integral multiple number r and available backoff times based on the number of times of signal retransmission n.
For example, the number of retransmissions n varies form 1 through 10. When the number of retransmissions n is 1, namely, at the first retransmission, variable k=min(1, 10)=1 and 0 less than r less than 21. Therefore, the integral multiple number r may be 0 or 1. Based on the selected value of the integral multiple number r the backoff time may be 0 times the slot time or 1 times the slot time.
At the 10th retransmission, variable k=min(10,10)=10 and 0 less than r  less than 210, so the integral multiple number r may be one of 0 to 1023. Therefore, the backoff time may be one of 0 times the slot time to 1023 times the slot time based on the selected integral multiple number r value optionally selected. At this time, the slot time in the 10M network is 52.4 ms.
If such method as described above is applied to a network having many nodes, some amount of scheduling fairness could be realized. The following description referring to FIG. 2 concerns the case that signals are transmitted in the related method in a network having a few active nodes. FIG. 2 illustrates a channel capture effect occurring when using a related backoff algorithm.
If the node A and the node B perform transmission of a packet at the same time, a collision of the packets occur. If the collision occurs, each of the nodes A and B determines a backoff time. If respective integral multiple number r values of nodes A and B are set to 0 and 1 respectively, the backoff time of node A becomes 0xc3x97 slot time, and the backoff time of node B becomes 1xc3x97 slot time. Accordingly, node A transmits a signal after waiting for only an IPG while node B waits for IPG +1xc3x97 slot time until the node A completes the packet transmission. Then node B waits for another IPG before transmitting its signal. According to such a scheme, node A can successfully transmit its packet without interference from node B.
Afterwards, if node A tries to successively transmit another packet, the packet collides with the first packet transmitted from node B. For node A which successfully transmitted its previous packet, this collision is the first collision for the successive packet, but the collision is the second collision for the first packet transmitted from node B. In other words, the number of times of signal retransmission, n, by the node A is less than the number of times of signal retransmission, n, by the node B. Therefore, there is low probability that the backoff time of node A is longer than the backoff time of node B. That is, the probability that node A can use the network is higher than the probability that node B can use the network. A problem exists that node A continuously transmits its packets while node B must only wait. This channel capture effect is more common when the conventional packet transmission method is applied to the LAN having a few active nodes.
Accordingly, when the related method is applied to a network having a few active nodes, there occurs the channel capture effect that one node must continuously wait while another node can continuously transmit packets, thus decreasing scheduling fairness of the network.
An object of the present invention is to substantially obviate one or more of the limitations and disadvantages of the related art.
Another object of the present invention is to improve scheduling fairness in using a network when collisions in an Ethernet based LAN occur during signal transmission.
A further object of the present invention is to increase overall network use efficiency.
To achieve these and other advantages, and in accordance with the purpose of the present invention as embodied and broadly described, a method for improving scheduling fairness for a network in accordance with a preferred embodiment of the invention includes detecting a packet collision occurring while different nodes transmit a packet; reading a previous network state for application of the backoff algorithm; selecting a new IPG based upon the read information; and determining a backoff time before retransmitting a packet.
The present invention can be achieved in a whole or in parts by a method for improving scheduling fairness in using a network by detecting whether or not collision occurs during packet transmission in the network having a plurality of nodes, and storing and monitoring signal transmit/receive state of X bit(s) before the collision with respect to each of the plurality of nodes. If the collision is detected, reading the previous transmit/receive state of X bit(s) with respect to a node having the collision, and judging the previous node state that has been read and setting an inter packet gap (IPG) for the node. After lapse of the IPG that has been set, effecting standard backoff. After lapse of a corresponding backoff time, retransmitting a signal of the node that has been collided. Detecting transmission collision with respect to the retransmitted signal of the node. If the collision is not detected with respect to the retransmitted signal of the node, updating the signal transmit/receive state of the node. If the collision is detected with respect to the retransmitted signal of the node, then repeating the steps of reading and judging previous node state, setting the IPG, effecting the standard backoff, retransmitting the signal, and detecting the collision.
The present invention can also be achieved in a whole or in parts by a method for scheduling transmissions from a plurality of nodes, including receiving a status of the node indicative of the successful transmission of a previous packet from the node; setting a length of time based on the status of the node; and transmitting a current packet to a system after waiting for the length of time.
The present invention can also be achieved in whole or in parts by a method for scheduling transmissions from a plurality of nodes, including detecting whether a collision occurs between transmitted signal during packet transmission in a network having a plurality of nodes. If the collision is not detected, transmitting a signal and updating the node state. If the collision is detected, reading a signal transmit/receive state of a node having the collision, and judging whether there is a difference between the signal transmit/receive state and a current state of the corresponding node. If there is no difference between the signal transmit/receive state and the current state, then retransmitting the signal after a backoff time, and detecting whether another collision occurs. If there is a difference between the signal transmit/receive state and the current states then setting an inter packet gap for the node based on the signal transmit/receive state. After a lapse of the inter packet gap and the backoff time, retransmitting the signal from the node having the collision and detecting whether a collision of the signal retransmitted from the node occurs. If the collision is not detected with respect to the retransmitted signal, updating the signal transmit/receive state of the node having the collision. If the collision is detected with respect to said retransmitted signal, and if there is no difference between the signal transmit/receive state and the current node state, then repeating step (d).
Additional advantages, objects, and features of the invention will be set forth in part in the description which follows and in part will become apparent to those having ordinary skill in the art upon examination of the following or may be learned from practice of the invention. The objects and advantages of the invention may be realized and attained as particularly pointed out in the appended claims.